1. Field of the Invention
The present invention generally relates to the fabrication and design of semiconductor chips and integrated circuits, and more specifically to routing tools which predict wire congestion.
2. Description of the Related Art
Integrated circuits are used for a wide variety of electronic applications, from simple devices such as wristwatches, to the most complex computer systems. A microelectronic integrated circuit (IC) chip can generally be thought of as a collection of logic cells with electrical interconnections between the cells, formed on a semiconductor substrate (e.g., silicon). An IC may include a very large number of cells and require complicated connections between the cells. A cell is a group of one or more circuit elements such as transistors, capacitors, resistors, inductors, and other basic circuit elements grouped to perform a logic function. Cell types include, for example, core cells, scan cells and input/output (I/O) cells. Each of the cells of an IC may have one or more pins, each of which in turn may be connected to one or more other pins of the IC by wires. The wires connecting the pins of the IC are also formed on the surface of the chip. For more complex designs, there are typically at least four distinct layers of conducting media available for routing, such as a polysilicon layer and three metal layers (metal-1, metal-2, and metal-3). The polysilicon layer, metal-1, metal-2, and metal-3 are all used for vertical and/or horizontal routing.
An IC chip is fabricated by first conceiving the logical circuit description, and then converting that logical description into a physical description, or geometric layout. This process is usually carried out using a “netlist,” which is a record of all of the nets, or interconnections, between the cell pins. A layout typically consists of a set of planar geometric shapes in several layers. The layout is then checked to ensure that it meets all of the design requirements, particularly timing requirements. The result is a set of design files known as an intermediate form that describes the layout. The design files are then converted into pattern generator files that are used to produce patterns called masks by an optical or electron beam pattern generator. During fabrication, these masks are used to pattern a silicon wafer using a sequence of photolithographic steps. The component formation requires very exacting details about geometric patterns and separation between them. The process of converting the specifications of an electrical circuit into a layout is called the physical design.
Cell placement in semiconductor fabrication involves a determination of where particular cells should optimally (or near-optimally) be located on the surface of a integrated circuit device. Due to the large number of components and the details required by the fabrication process for very large scale integrated (VLSI) devices, physical design is not practical without the aid of computers. As a result, most phases of physical design extensively use computer-aided design (CAD) tools, and many phases have already been partially or fully automated. Automation of the physical design process has increased the level of integration, reduced turn around time and enhanced chip performance. Several different programming languages have been created for electronic design automation (EDA), including Verilog, VHDL and TDML.
Physical synthesis is prominent in the automated design of integrated circuits such as high performance processors and application specific integrated circuits (ASICs). Physical synthesis is the process of concurrently optimizing placement, timing, power consumption, crosstalk effects and the like in an integrated circuit design. This comprehensive approach helps to eliminate iterations between circuit analysis and place-and-route. Physical synthesis has the ability to repower gates, insert buffers, clone gates, etc., so the area of logic in the design remains fluid. However, physical synthesis can take days to complete.
Routability is a key factor when performing floorplanning or trying to close on timing via physical synthesis. A designer can expend considerable effort trying to get the design into a good state in terms of timing and signal integrity, only to subsequently find that it is unroutable. Ideally, the designer should be able to invoke a snapshot routability analysis that allows him or her to understand the routability issues involved from making floorplanning or optimization decisions.
During physical synthesis, wire congestion may be examined as part of the routing process. Circuit designers have devised various routing tools to provide reliable congestion information when designing the circuit, including empirical models, global routers, and probabilistic analysis. Among these, only probabilistic routing congestion analysis is particularly efficiently, since it avoids actually performing global routing. Instead, for a given placement, it examines the set of nets in the design and uses probability theory to compute the expected congestion for each routing tile.
In one probabilistic analysis algorithm, all possible pin-to-pin routes within the bounding box of the pins are considered, and each route is assigned an equal usage probability. This approach invariably produces biased congestion towards the middle of the bounding box instead of the periphery. Since routers usually try to minimize the insertion of vias, the periphery of the bounding box actually has more congestion than the interior, so this approach can lead to unsatisfactory results.
In another approach, the probabilistic analysis depends on the different types (shapes) of the routes. Every net is classified into one of four different categories: short nets, flat nets, L-shaped nets, and Z-shaped nets. These types of nets are illustrated in FIG. 1. A short net 2 is a net that locates in one tile or bin. A flat net 4 spans at most one tile in either the vertical or horizontal direction. An L-shaped net 6 or a Z-shaped net 8 spans more than one tile in either direction and have one or two bends, respectively. Probabilistic routing analysis is done exclusively for two-pin nets. Multi-pin nets are broken up into sets of two-pin nets by constructing a tree over the pins. For each net, a number of likely paths is considered and the probabilistic usages are assigned to each bin in the bounding box of the net. The net can be seen as spreading over its possible paths where each path has the same probability. Routing congestion is defined as the ratio of usage to capacity.
While this approach leads to better probabilistic routing usage along the boundary of a net's bounding box, it still does not adequately address the problem of wiring blockages. Before global routing occurs, several requirements may stake claim to wiring resources which then become fixed for global routing. These requirements include local wiring on the bottom layers for the internal pin connections of a gate, power grids on multiple layers, pre-routed clock wires, planned buses, or datapaths, and hierarchical logic, memory, or propriety (IP) blocks. Those features may already have been completely routed; even if not, their routes may be hidden from the top-level routing congestion map. The corresponding bins are unlikely to block 100% of the routing resources since generally there will be some routing resources allocated on the top layers.
Wiring blockage for a given bin can be complete, or partial. Complete blockages can be handled by simply omitting the bin from the possible paths. In practice, however, blockages with absolutely no available tracks are rarely seen, and previous approaches fail to realistically model that essentially every tile of a routing congestion map is neither completely empty or completely full. There is almost always some amount of wiring blockage that a global router will take into account, yet probabilistic routers do not take this reality into account. In conventional probabilistic analysis, if there are partial blockages in some bins, the usage of these bins is not changed at all. Rather, a simple model is applied in which the number of blocked tracks are subtracted from the capacity of the bin. A global router is thus more likely to route a net in a lower congestion region than in a higher one.
In light of the foregoing, it would be desirable to devise an improved probabilistic method of predicting wire congestion which provides a practical approach to handling partial wiring blockages. It would be further advantageous if the method could improve the complexity the probabilistic analysis while still maintaining quality routing solutions.